package leetcode.editor.cn;

import java.util.*;

class PermutationsIi {
    public static void main(String[] args) {
        Solution solution = new PermutationsIi().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            if (nums.length == 0) {
                return res;
            }
            Arrays.sort(nums);
            backtracking(nums, new boolean[nums.length]);
            return res;
        }

        List<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();

        public void backtracking(int[] nums, boolean[] used) {
            if (path.size() == nums.length) {
                res.add(new ArrayList<>(path));
                return;
            }

            for (int i = 0; i < nums.length; i++) { // 排列从0开始
                // used[i - 1] == true，说明同一树枝nums[i - 1]使用过
                // used[i - 1] == false，说明同一树层nums[i - 1]使用过
                // 如果同一树层nums[i - 1]使用过则直接跳过
                // 注意需要排列
                if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {  // 后一个在同一层判断上一个是否使用过
                    continue;
                }

                // 此时时used[i]判断这个元素是否使用过（树枝去重）
                if (used[i] == true) {
                    continue;       // 前一个判断path中是否使用过
                }

                path.add(nums[i]);
                used[i] = true;
                backtracking(nums, used);
                used[i] = false;
                path.removeLast();
            }

            /**
             * 哈希法
             *
             * @param nums
             * @param used
             */
        /*public void backtracking(int[] nums, boolean[] used) {
            if (path.size() == nums.length) {
                res.add(new ArrayList<>(path));
                return;
            }

            Set<Integer> set = new HashSet<>();
            for (int i = 0; i < nums.length; i++) {
                // 树层去重
                if (set.contains(nums[i])) {
                    continue;
                }
                // 枝干去重
                if (used[i] == true) {
                    continue;
                }
                set.add(nums[i]);
                used[i] = true;
                path.add(nums[i]);
                backtracking(nums, used);
                used[i] = false;    // 回溯
                path.removeLast();
            }
        }*/
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
